package 简单.动态规划.数组区间;

/**
 * 给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内
 * 元素的总和，包含 i、j 两点。
 * <p>
 * 实现 NumArray 类：
 * <p>
 * NumArray(int[] nums) 使用数组 nums 初始化对象
 * int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）
 * 范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1]
 * , ... , nums[j])）
 * <p>
 * 来源：https://leetcode-cn.com/problems/range-sum-query-immutable/description/
 */
public class 区域和检索_数组不可变_303 {

    public static void main(String[] args) {

        int[] nums = {0, 1, 2, 3};
        NumArray numArray = new NumArray(nums);
        System.out.println(numArray.sumRange(2, 3));
    }

    /**
     * 先求出从0开始到达num的某一个元素的和
     * 从索引i到j元素范围内总和=从0到j元素的总和-从0到i-1元素的总和
     * 需要i索引的元素，所以i-1
     * dp[right] - dp[left - 1]
     * 当left=0的时候会有数组越界异常,需要判断
     */
    static class NumArray {

        int[] dp;

        public NumArray(int[] nums) {
            dp = new int[nums.length];
            dp[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = dp[i - 1] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return left == 0 ? dp[right] : dp[right] - dp[left - 1];
        }
    }

}
